#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0027.py
@time: 2021/9/27 21:03
@desc: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
'''


class Solution:
    def exist(self, board: list, word: str) -> bool:
        m, n = len(board), len(board[0])
        choices = [(0, 1), (0, -1), (-1, 0), (1, 0)]

        def found(track, word):
            return ''.join(track) == word

        def hit(track, word):
            l = len(track)
            if l == 0:
                return False
            for i in range(l):
                if not track[i] == word[i]:
                    return False
            return True

        def backtrack(track, row, col, visited):
            # if row >= m or col >= n or row < 0 or col < 0:
            #     return
            track.append(board[row][col])
            if found(track, word):
                return True
            if hit(track, word):
                visited[row][col] = True
                for dir in choices:
                    if row + dir[0] >= m or col + dir[1] >= n or row + dir[0] < 0 or col + dir[1] < 0 or visited[row + dir[0]][col + dir[1]]:
                        continue
                    flag = backtrack(track, row + dir[0], col + dir[1], visited)
                    if flag:
                        return flag
                    else:
                        if not track:
                            return False
                        visited[row][col] = False
                        track.pop()
        for i in range(m):
            for j in range(n):
                track = []
                visited = [[False for _ in range(n)] for _ in range(m)]
                flag = backtrack(track, i, j, visited)
                if flag:
                    return flag
        return False


if __name__ == '__main__':
    # board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
    # word = "ABCCED"
    # board = [["a","b"]]
    # word = "ba"
    # board = [["a", "b"], ["c", "d"]]
    # word = "abcd"

    # board = [["a"]]
    # word = "ab"
    # board = [["a","a"]]
    # word = "aaa"
    # board = [["C","A","A"],["A","A","A"],["B","C","D"]]
    # word = "AAB"
    board = [["A","B","C","E"],["S","F","E","S"],["A","D","E","E"]]
    word = "ABCESEEEFS"
    res = Solution().exist(board, word)
    print(res)
